package tpcomp2010.estructura;

import java.util.ArrayList;

/**
 * Clase SUbconjunto, contiene todas las operaciones necesarias para convertir
 * un AFN a un AFD
 */
public class SubConjunto {
    /**
     * Automanta que procesa el Algoritmo SubConjunto
     */
    Automata elAutomata;

    /**
     * Matriz de transicion
     */
    private MatrizTransicion dtrans;

    /**
     * Tabla D Estados.
     */
    ArrayList<ListaNodos> DEstados;

    /**
     * Class constructor Especificando el Automata que va procesar
     * @param AFN Automata que procesará el algoritmo
     */
    public SubConjunto(Automata AFN) {
        this.elAutomata = AFN;
        dtrans = new MatrizTransicion();
        DEstados = new ArrayList();
    }

    /**
     * FUncion principal, ejecuta el algoritmo de subconjunto
     * @return Una Matriz de transicion
     * @throws Exception
     */
    public MatrizTransicion ejecutar() throws Exception{
        Token simbolo;
        ListaNodos U;
        
        Nodo nodoInicial = elAutomata.getNodos().getNodoInicial();
        ListaNodos listaNodos = e_cerradura(nodoInicial, new ListaNodos());
        listaNodos.setId(0);
        DEstados.add(listaNodos);
    
        while (hayNodosSinMarcar()){
            MatrizTransicionKey clave;
            ListaNodos T = nodoSinMarcar();
            T.setMarcado(true);
            for (String cad : elAutomata.getAlfabeto()) {
                simbolo = new Token(cad);
                U = e_cerradura(mover(T, simbolo));
                if(U == null){
                    continue;
                }
                int id_U = estaEnDEstados(U);
                if(id_U == -1){
                    U.setMarcado(false);
                    U.setId(DEstados.size());
                    DEstados.add(U);
                }else{
                    U.setId(id_U);
                }
                clave = new MatrizTransicionKey(T,simbolo);
                dtrans.setValor(clave, U);
            }
        }
        return this.dtrans;
    }

    /**
     * Funcion que calcula la e_cerradura de un nodo
     * @return Una Lista de Nodos qu erepresenta al conjunto e_cerradura de s
     * @param s Nodo sobre el cual se calculará la e_cerradura
     * @param listaActual
     * @return La lista de nodos resultante de calcular la e_cerradura
     */
    public static ListaNodos e_cerradura(Nodo s, ListaNodos listaActual) {
        ListaNodos listaNueva = null;
        for (Arista e : s.getAristas()) {
            if(e.getEtiqueta().compareTo(Constantes.getSimboloVacio()) == 0){
                listaNueva = e_cerradura(e.getNodoDestino(), listaActual);
                listaActual = mergeListas(listaActual, listaNueva );
                
            }
        }
        listaActual.insertar(s);
        return listaActual;
    }

    /**
     * Funcion que calcula la e_cerradura de una lista de nodos
     * @param T ListaNodos de la cual se va calcular su e_cerradura
     * @return La lista de nodos resultante de calcular la e_cerradura
     */
    public static ListaNodos e_cerradura(ListaNodos T){
        if(T == null){
            return null;
        }
        
        ListaNodos listaNodos = new ListaNodos();
        for (Nodo act : T) {
            listaNodos = mergeListas(listaNodos, e_cerradura(act, new ListaNodos()));
        }
        
        return listaNodos;
    }

    /**
     * Funcion que calcula los nodos destinos de una lista de nodos dado un token
     * @param T Lista de nodos que se moveran
     * @param a el token con el que se van a mover
     * @return Lista de nodos destinos
     */
    public static ListaNodos mover(ListaNodos T, Token a){
        ListaNodos lista = new ListaNodos();
        
        for (Nodo nodo : T) {
            for (Arista enlace : nodo.getAristas()) {
                if(enlace.getEtiqueta().compareTo(a.getValor()) == 0){
                    lista.insertar(enlace.getNodoDestino());
                }
            }
        }
        if(lista.size() == 0){
            return null;
        }else{
            return lista;
        }
    }

    /**
     * Verifica si exiten nodos sin marcar en DEstados
     * @return true si existen nodos sin marcar, false en caso contrario
     */
    private boolean hayNodosSinMarcar(){
        for (ListaNodos listaNodos : DEstados) {
            if(!listaNodos.isMarcado()){
                return true;
            }
        }
        return false;
    }

    /**
     * Devuelve los nodos sin marcar
     * @return lista de nodos sin marcar.
     * @throws Exception
     */
    private ListaNodos nodoSinMarcar() throws Exception{
        for (ListaNodos listaNodos : DEstados) {
            if(!listaNodos.isMarcado()){
                return listaNodos;
            }
        }
        throw new Exception("No hay Lista de Estados sin marcar en Destados.");
    }

    /**
     * Verifica si una lista de nodos se encuenta en DEstados
     * @param U Lista a verificar si se encuentra en DEstados
     * @return -1 si no se encuentra, en caso contrario devuelve el ID de la lista de nodos
     */
    private int estaEnDEstados(ListaNodos U){
        for (ListaNodos lista : DEstados) {
            if(lista.compareTo(U) == 0){
                return lista.getId();
            }
        }
        return -1;
    }

    /**
     * Funcion que mezcla dos listas, sin repetir los nodos
     * @param A primera lista
     * @param B Segunda lista
     * @return una nueva lista de nodos con las listas ya mezcladas
     */
    public static ListaNodos mergeListas(ListaNodos A, ListaNodos B){
        ListaNodos listaNodos = new ListaNodos();
        
        if(A != null){
            for (Nodo nodo : A) {
                try{
                    listaNodos.getNodoById(nodo.getId());
                }catch(Exception ex){
                    listaNodos.insertar(nodo);
                }
            }
        }

        if(B != null){
            for (Nodo nodo : B) {
                try{
                    listaNodos.getNodoById(nodo.getId());
                }catch(Exception ex){
                    listaNodos.insertar(nodo);
                }
            }
        }

        return listaNodos;
    }

    /**
     * Visita de forma recursiva el Automata
     * @param actual Nodo actual visitado
     */
    public static void visitarRecursivo(Nodo actual){
        if(!actual.isVisitado()){
            actual.setVisitado(true);
            for (Arista enlace : actual.getAristas()) {
                visitarRecursivo(enlace.getNodoDestino());
            }
        }
    }
    
}
